class Solution
{
public:
    // 应该是对的, 但是会超时
    int maxIncreasingCells(vector<vector<int>> &mat)
    {
        int m = mat.size();
        int n = mat[0].size();

        vector<map<int, unordered_set<int>>> rowEdges(m);
        vector<int> rowMinVals(m);
        for (int row = 0; row < m; ++row)
        {
            map<int, unordered_set<int>> &rowValIndex = rowEdges[row];
            for (int col = 0; col < n; ++col)
            {
                rowValIndex[mat[row][col]].insert(col);
            }
            rowMinVals[row] = rowValIndex.begin()->first;
        }

        vector<map<int, unordered_set<int>>> colEdges(n);
        vector<int> colMinVals(n);
        for (int col = 0; col < n; ++col)
        {
            map<int, unordered_set<int>> &colValIndex = colEdges[col];
            for (int row = 0; row < m; ++row)
            {
                colValIndex[mat[row][col]].insert(row);
            }
            colMinVals[col] = colValIndex.begin()->first;
        }

        int maxVisitCount = 1;
        for (int row = 0; row < m; ++row)
        {
            for (int col = 0; col < n; ++col)
            {
                if (rowMinVals[row] == colMinVals[col] && rowMinVals[row] == mat[row][col])
                {
                    queue<pair<int, int>> q;
                    q.push({row, col});
                    int step = 0;
                    while (!q.empty())
                    {
                        int qSize = q.size();
                        for (int _ = 0; _ < qSize; _++)
                        {
                            auto [i, j] = q.front();
                            q.pop();
                            int val = mat[i][j];
                            auto rowNext = rowEdges[i].upper_bound(val);
                            if (rowNext != rowEdges[i].end())
                            {
                                for (int jNext : rowNext->second)
                                {
                                    q.push({i, jNext});
                                }
                            }
                            auto colNext = colEdges[j].upper_bound(val);
                            if (colNext != colEdges[j].end())
                            {
                                for (int iNext : colNext->second)
                                {
                                    q.push({iNext, j});
                                }
                            }
                        }
                        ++step;
                    }

                    maxVisitCount = max(maxVisitCount, step);
                }
            }
        }
        return maxVisitCount;
    }
};